﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.StringCode
{
    class KMPString
    {
        // ================================= KMP算法
        //KMP主要应用在字符串匹配上
        //KMP的经典思想是：当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配
        //next数组是一个前缀表，用来回退，记录了模式串与主串不匹配的时候，模式串应该从哪里开始重新匹配。
        //前缀表:记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。
        //前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串
        //后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串



        //================================ 力扣28 实现strStr()
        //给定两个字符串haystack和needle，请你在haystack字符串中找出needle字符串出现的第一个位置（下标从0开始）。
        //如果不存在，则返回-1
        //输入：haystack = "hello",needle = "ll"
        //输入：2
        public int StrStr(string haystack, string needle)
        {
            if (needle.Length == 0)
                return 0;

            int[] next = new int[needle.Length];
            getNext(next, needle);
            int j = -1;
            for(int i = 0;i<haystack.Length;i++)
            {
                while (j >= 0 && haystack[i] != needle[j + 1])
                    j = next[j];
                if (haystack[i] == needle[j + 1])
                    j++;
                if (j == needle.Length - 1)
                    return i - needle.Length + 1;
            }
            return -1;
        }
        private void getNext(int[] next, string s)
        {
            int j = -1;
            next[0] = j;
            for(int i = 1;i<s.Length;i++)
            {
                while (j >= 0 && s[i] != s[j + 1])
                    j = next[j];

                if (s[i] == s[j + 1])
                    j++;
                next[i] = j;
            }
        }

    }
}
